package path;
import java.util.*;
public class Dijkstra {
    static class Graph {
        private int V; // 图中的节点数
        private List<Edge>[] adj; // 邻接表表示图的连接关系

        public Graph(int v) {
            V = v;
            adj = new ArrayList[v];
            for (int i = 0; i < v; ++i) {
                adj[i] = new ArrayList<>();
            }
        }

        // 添加有向边
        public void addEdge(int src, int dest, int weight) {
            adj[src].add(new Edge(dest, weight));
        }

        // 迪杰斯特拉算法
        public int[] dijkstra(int start) {
            int[] dist = new int[V];
            Arrays.fill(dist, Integer.MAX_VALUE);
            dist[start] = 0;

            PriorityQueue<Edge> minHeap = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
            minHeap.offer(new Edge(start, 0));

            while (!minHeap.isEmpty()) {
                Edge current = minHeap.poll();
                int u = current.dest;

                for (Edge neighbor : adj[u]) {
                    int v = neighbor.dest;
                    int weight = neighbor.weight;

                    if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
                        dist[v] = dist[u] + weight;
                        minHeap.offer(new Edge(v, dist[v]));
                    }
                }
            }

            return dist;
        }

        private class Edge {
            int dest;
            int weight;

            Edge(int dest, int weight) {
                this.dest = dest;
                this.weight = weight;
            }
        }
    }


    public static void main(String[] args) {
        int V = 5;
        int start = 0;
        Graph graph = new Graph(V);

        // 添加有向边和权重
        graph.addEdge(0, 1, 2);
        graph.addEdge(0, 3, 1);
        graph.addEdge(1, 2, 3);
        graph.addEdge(1, 3, 2);
        graph.addEdge(3, 4, 4);
        graph.addEdge(4, 2, 1);

        int[] shortestDistances = graph.dijkstra(start);

        for (int i = 0; i < V; i++) {
            System.out.println("从节点 " + start + " 到节点 " + i + " 的最短距离是 " + shortestDistances[i]);
        }
    }
}


